/*
 * @lc app=leetcode.cn id=1269 lang=typescript
 *
 * [1269] 停在原地的方案数
 */

// @lc code=start
function numWays(steps: number, arrLen: number): number {
  const mod = 10 ** 9 + 7;
  // 下标移动的范围不能超过steps
  // 这里可以限制一下下标的范围，做个优化
  const limit = Math.min(arrLen - 1, steps);

  const dp = new Array(steps + 1).fill(0).map(() => new Array(limit + 1).fill(0));
  dp[0][0] = 1;

  for (let i = 1; i <= steps; i++) {
    for (let j = 0; j <= limit; j++) {
      // 原地
      dp[i][j] = dp[i - 1][j];
      // 左移
      if (j - 1 >= 0) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
      }
      // 右移
      if (j + 1 <= limit) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
      }
    }
  }

  return dp[steps][0];
}
// @lc code=end
